#include <string.h>
#include <stdio.h>

#define HASHINT

#ifdef HASHINT
	typedef int HashRetType;
	#define HASHCONST 1103515245
#else
	typedef long long HashRetType;
	#define HASHCONST 6364136223846793005
#endif

HashRetType hashn(const char* str, int n)
{
	HashRetType val = 0;
	for (int ii = 0; ii < n; ii++)
	{
		val += str[ii];
		val *= HASHCONST;
	}
	return val;
}

#define RK_MAX_NUM_STRS 50

int RKStrLen, RKNumStr;
HashRetType RKStrHashes[RK_MAX_NUM_STRS], RKOffset;

void init_rk(int len, int numstr, const char **strings)
{
	RKStrLen = len;
	RKNumStr = numstr;
	for(int ii = 0; ii < numstr; ii++)
		RKStrHashes[ii] = hashn(strings[ii], len),
	
	RKOffset = 1;
	for(int ii = 0; ii <= len; ii++)
		RKOffset *= HASHCONST;
}

int RK_check(HashRetType hash, const char* str, const char** strings)
{
	for (int ii = 0; ii < RKNumStr; ii++)
		if (hash == RKStrHashes[ii])
			if (strncmp(strings[ii], str, RKStrLen) == 0)
				return ii;
	return -1;
}

// Returns -1 if no matches, ii for string otherwise.
int run_rk(const char *str, int strlen, const char **strings)
{
	if (strlen < RKStrLen)
		return -1;

	HashRetType thash;
	thash = hashn(str, RKStrLen);
	if (int retval = RK_check(thash, str, strings) != -1)
		return retval;

	for (int ii = 0; ii < strlen - RKStrLen; ii++)
	{
		thash += str[ii+RKStrLen];
		thash *= HASHCONST;
		thash -= RKOffset * str[ii];
		if (int retval = RK_check(thash, &str[ii+1], strings) != -1)
			return retval;
	}
	return -1;
}

int main()
{
	const char *strings[3];
	strings[0] = (const char *)"foobar1";
	strings[1] = (const char *)"experts";
	strings[2] = (const char *)"fredric";

	init_rk(7, 3, strings);
	char * str = (char*) "The Quick Brown fox jumped over the lazy foobar1";
	printf("%d\n", run_rk(str, 48, strings));

	return 0;
}
